1 00:00:00,000 --> 00:00:02,770 NARRATOR: The following content is provided by MIT 2 00:00:02,770 --> 00:00:06,090 OpenCourseWare under a Creative Commons license. 3 00:00:06,090 --> 00:00:08,680 Additional information about our license and MIT 4 00:00:08,680 --> 00:00:11,930 OpenCourseWare in general is available at ocw.mit.edu. 5 00:00:11,930 --> 00:00:15,500 6 00:00:15,500 --> 00:00:17,730 PROFESSOR: Finite difference methods for initial value 7 00:00:17,730 --> 00:00:23,670 problems that we're coming to the end of and the solving 8 00:00:23,670 --> 00:00:26,990 large systems that we're coming to the beginning of was 9 00:00:26,990 --> 00:00:37,140 to talk today about matrices, because that language is just 10 00:00:37,140 --> 00:00:38,390 useful for everything. 11 00:00:38,390 --> 00:00:40,830 12 00:00:40,830 --> 00:00:46,410 So about the homeworks, Mr. Cho put in a long weekend 13 00:00:46,410 --> 00:00:50,090 grading the homeworks that were turned in Friday and 14 00:00:50,090 --> 00:00:56,550 preparing code and output to go up on the web page, 15 00:00:56,550 --> 00:00:58,980 probably late tonight or tomorrow. 16 00:00:58,980 --> 00:01:06,220 So have a look to see and I hope that those codes will be 17 00:01:06,220 --> 00:01:08,470 useful for the future too. 18 00:01:08,470 --> 00:01:09,740 Right. 19 00:01:09,740 --> 00:01:14,350 So we'll maybe say more about the outputs and about the 20 00:01:14,350 --> 00:01:19,260 projects, which by the way, could grow out of that 21 00:01:19,260 --> 00:01:23,250 homework or could go in a totally different direction. 22 00:01:23,250 --> 00:01:28,750 I'm thinking that the right time to say projects due would 23 00:01:28,750 --> 00:01:31,200 be after spring break. 24 00:01:31,200 --> 00:01:36,100 So pretty much nearly immediately after the spring 25 00:01:36,100 --> 00:01:38,880 break would be -- and we'll talk about it more, but just 26 00:01:38,880 --> 00:01:40,780 so you have an idea of what's -- 27 00:01:40,780 --> 00:01:44,120 what timetable I had in mind. 28 00:01:44,120 --> 00:01:45,370 So, matrices then. 29 00:01:45,370 --> 00:01:49,010 30 00:01:49,010 --> 00:01:52,780 In particular, finite difference matrices. 31 00:01:52,780 --> 00:01:59,350 So that's the second difference matrix, k, and I'll 32 00:01:59,350 --> 00:02:04,210 frequently use that letter k as I did in 18.085 for that 33 00:02:04,210 --> 00:02:07,630 very, very important and useful matrix. 34 00:02:07,630 --> 00:02:09,940 So what are its properties? 35 00:02:09,940 --> 00:02:11,190 it's tridiagonal. 36 00:02:11,190 --> 00:02:13,360 37 00:02:13,360 --> 00:02:16,200 That's a very important property, which we'll see 38 00:02:16,200 --> 00:02:20,280 because that means that computations solving linear 39 00:02:20,280 --> 00:02:25,420 systems are very fast with a tridiagonal matrix. 40 00:02:25,420 --> 00:02:27,740 It's symmetric. 41 00:02:27,740 --> 00:02:31,730 All its Eigen values are positive, so I would say it's 42 00:02:31,730 --> 00:02:36,110 symmetric positive definite and those Eigen values and 43 00:02:36,110 --> 00:02:37,030 Eigen vectors -- 44 00:02:37,030 --> 00:02:40,490 so the Eigen vectors for this matrix turn out 45 00:02:40,490 --> 00:02:43,280 to be discrete -- 46 00:02:43,280 --> 00:02:47,510 not quite discrete exponentials, discrete sines, 47 00:02:47,510 --> 00:02:49,670 discrete sine function. 48 00:02:49,670 --> 00:02:52,780 If I change the boundary conditions, I can get discrete 49 00:02:52,780 --> 00:02:56,320 cosines as the Eigen vectors or I could get discrete 50 00:02:56,320 --> 00:03:00,620 exponentials as the Eigen vectors by making it periodic. 51 00:03:00,620 --> 00:03:03,200 Maybe I'll mention how to make it periodic and then I'll 52 00:03:03,200 --> 00:03:05,390 erase it again. 53 00:03:05,390 --> 00:03:09,550 To make it periodic means that this second different centered 54 00:03:09,550 --> 00:03:14,690 at point 1 should look ahead to point 2 and look behind to 55 00:03:14,690 --> 00:03:18,030 point 0, but that'll be the same as point n, so I would 56 00:03:18,030 --> 00:03:22,600 put a minus 1 in that corner and this one similarly, it 57 00:03:22,600 --> 00:03:28,350 looks ahead, which really brings it around again, since 58 00:03:28,350 --> 00:03:32,470 we're sort of on a circle, brings it around again here. 59 00:03:32,470 --> 00:03:37,060 So that matrix now with minus 1s added in the corner, I 60 00:03:37,060 --> 00:03:39,970 would call c, a circular. 61 00:03:39,970 --> 00:03:46,150 So I'll leave the letter k there, but the right letter is 62 00:03:46,150 --> 00:03:50,920 c while these minus 1s are here to make it periodic. 63 00:03:50,920 --> 00:03:54,370 By the way, they mess up that the tridiagonal. 64 00:03:54,370 --> 00:03:56,690 It's no longer tridiagonal. 65 00:03:56,690 --> 00:03:58,670 Also, it certainly got -- 66 00:03:58,670 --> 00:03:59,920 it's very sparse. 67 00:03:59,920 --> 00:04:03,390 68 00:04:03,390 --> 00:04:09,220 Mentioning sparse reminds me, if you're coding large 69 00:04:09,220 --> 00:04:13,590 matrices that are sparse, you should let MATLAB know that 70 00:04:13,590 --> 00:04:14,640 they're sparse. 71 00:04:14,640 --> 00:04:17,520 So MATLAB lab has a whole -- 72 00:04:17,520 --> 00:04:21,200 it carries out operations, if you tell it it's a sparse 73 00:04:21,200 --> 00:04:29,210 matrix, then it only operates where the non 0s are located 74 00:04:29,210 --> 00:04:34,370 and it doesn't waste its time looking at these 0s, these 0s 75 00:04:34,370 --> 00:04:36,840 through all the matrix steps. 76 00:04:36,840 --> 00:04:42,300 77 00:04:42,300 --> 00:04:46,350 So using sparse MATLAB is important thing 78 00:04:46,350 --> 00:04:47,380 to know about it. 79 00:04:47,380 --> 00:04:50,190 It just typically and s or an sp will 80 00:04:50,190 --> 00:04:53,070 appear in MATLAB commands. 81 00:04:53,070 --> 00:04:56,700 For example, I'll just maybe fill it in here. 82 00:04:56,700 --> 00:04:59,050 What's the sparse identity matrix? 83 00:04:59,050 --> 00:05:04,470 The normal identity matrix would be i of n and the sparse 84 00:05:04,470 --> 00:05:09,620 identity matrix is sp, speye of n. 85 00:05:09,620 --> 00:05:14,030 Similarly, we would create k -- 86 00:05:14,030 --> 00:05:19,860 we could use 2 times speye of n as the diagonal of k and the 87 00:05:19,860 --> 00:05:24,910 two, the upper and lower diagonals -- 88 00:05:24,910 --> 00:05:28,670 and we could tell it these two entries. 89 00:05:28,670 --> 00:05:29,920 Another thing to say -- 90 00:05:29,920 --> 00:05:32,440 91 00:05:32,440 --> 00:05:34,960 what I said I wasn't going to do, I'll do because I hate to 92 00:05:34,960 --> 00:05:37,950 see a k up there while it's not right. 93 00:05:37,950 --> 00:05:41,510 94 00:05:41,510 --> 00:05:46,460 Two more points about this matrix. 95 00:05:46,460 --> 00:05:49,060 It's singular now. 96 00:05:49,060 --> 00:05:52,070 The determinate is 0. 97 00:05:52,070 --> 00:05:54,370 Now I'm never going to take the 98 00:05:54,370 --> 00:05:57,200 determinate of a giant matrix. 99 00:05:57,200 --> 00:05:59,810 That's a bad thing to do. 100 00:05:59,810 --> 00:06:08,620 Much better to recognize that there's a vector, x, let's say 101 00:06:08,620 --> 00:06:11,010 and it's the vector of all 1s. 102 00:06:11,010 --> 00:06:13,040 It's the vector of n 1s. 103 00:06:13,040 --> 00:06:16,580 If you imagine multiplying this matrix by the vector of n 104 00:06:16,580 --> 00:06:19,720 1s, what do you get? 105 00:06:19,720 --> 00:06:22,760 You get all 0s. 106 00:06:22,760 --> 00:06:27,310 So that vector of all 1s is in the null space, I would say, 107 00:06:27,310 --> 00:06:28,030 of a matrix. 108 00:06:28,030 --> 00:06:32,650 Null space is just the vectors that get wiped out by the 109 00:06:32,650 --> 00:06:36,080 matrix. cx is all 0. 110 00:06:36,080 --> 00:06:42,550 So that vector, this matrix has some non 0 vectors in its 111 00:06:42,550 --> 00:06:44,040 null space. 112 00:06:44,040 --> 00:06:47,290 I know right away then, its determinate is 0. 113 00:06:47,290 --> 00:06:52,260 So the determinate of that is 0 and now that would tell me 114 00:06:52,260 --> 00:06:56,020 something about the Eigen values of the matrix. 115 00:06:56,020 --> 00:06:59,430 It tells me about one Eigen value. 116 00:06:59,430 --> 00:07:02,410 It's 0. 117 00:07:02,410 --> 00:07:10,170 A matrix, like c, that has cx equals 0 -- 118 00:07:10,170 --> 00:07:14,400 I could also say that that cx equals 0 x. 119 00:07:14,400 --> 00:07:16,060 That would actually be better, so that 120 00:07:16,060 --> 00:07:19,230 both sides are vectors. 121 00:07:19,230 --> 00:07:25,050 So I'm realizing that that vector in the null space is an 122 00:07:25,050 --> 00:07:27,350 Eigen vector and the corresponding 123 00:07:27,350 --> 00:07:28,990 Eigen value is 0. 124 00:07:28,990 --> 00:07:36,590 125 00:07:36,590 --> 00:07:40,140 Otherwise, the Eigen values will all still be positive. 126 00:07:40,140 --> 00:07:45,250 So this would be a positive semidefinite. 127 00:07:45,250 --> 00:07:51,770 I would call that matrix positive semidefinite, the 128 00:07:51,770 --> 00:07:56,480 semi telling me that it isn't quite definite, that it gets 129 00:07:56,480 --> 00:07:59,090 down and has 0. 130 00:07:59,090 --> 00:08:02,880 131 00:08:02,880 --> 00:08:06,710 The matrix is singular, but still it's good to know where 132 00:08:06,710 --> 00:08:09,510 all the other n minus 1 Eigen values are. 133 00:08:09,510 --> 00:08:10,760 They're all positive. 134 00:08:10,760 --> 00:08:13,660 135 00:08:13,660 --> 00:08:16,600 About the bandwidth -- 136 00:08:16,600 --> 00:08:19,380 let me go back to k now. 137 00:08:19,380 --> 00:08:22,010 Because the bandwidth, strictly speaking, the 138 00:08:22,010 --> 00:08:25,770 bandwidth of c is very large. 139 00:08:25,770 --> 00:08:32,040 the bandwidth is, if I'm looking for only one number, 140 00:08:32,040 --> 00:08:37,440 that number tells me how many diagonals I have to grow until 141 00:08:37,440 --> 00:08:44,100 I reach the last non 0. 142 00:08:44,100 --> 00:08:54,640 So the bandwidth here is large and in general, the operation 143 00:08:54,640 --> 00:08:59,930 count, the amount of work to do, is going 144 00:08:59,930 --> 00:09:02,100 to grow with a bandwidth. 145 00:09:02,100 --> 00:09:07,230 Of course, not having full bandwidth isn't quite the full 146 00:09:07,230 --> 00:09:10,080 story for this matrix, because it's so sparse. 147 00:09:10,080 --> 00:09:15,090 I've got hundreds of 0 diagonals in between 148 00:09:15,090 --> 00:09:16,380 and just this one. 149 00:09:16,380 --> 00:09:21,500 Anyway, this is a matrix with a large bandwidth, but a 150 00:09:21,500 --> 00:09:23,070 little deceptive. 151 00:09:23,070 --> 00:09:29,120 Now here's the matrix with a -- back to k again. 152 00:09:29,120 --> 00:09:34,030 I call the bandwidth just 1 here. 153 00:09:34,030 --> 00:09:37,820 Really, maybe half bandwidth would be a better word. 154 00:09:37,820 --> 00:09:46,280 The bandwith is the number of diagonals above or below -- 155 00:09:46,280 --> 00:09:50,360 take the maximum of the count above and the count below and 156 00:09:50,360 --> 00:09:53,210 in this case, both counts are 1. 157 00:09:53,210 --> 00:09:56,810 1 diagonal above, 1 diagonal below, so really, half 158 00:09:56,810 --> 00:10:01,550 bandwidth, I would say, is 1. 159 00:10:01,550 --> 00:10:04,620 Just some convention is needed there. 160 00:10:04,620 --> 00:10:11,500 The crucial point is that the bandwidth measures the amount 161 00:10:11,500 --> 00:10:18,420 of work to do when you do elimination, as MATLAB will 162 00:10:18,420 --> 00:10:21,170 do, of course. 163 00:10:21,170 --> 00:10:22,470 One other -- 164 00:10:22,470 --> 00:10:23,520 the thing about MATLAB -- 165 00:10:23,520 --> 00:10:27,970 so I'm often referring to MATLAB and I'm thinking of its 166 00:10:27,970 --> 00:10:29,430 backslash command. 167 00:10:29,430 --> 00:10:38,990 The backslash, which solves ax equal b by just a backslash b. 168 00:10:38,990 --> 00:10:42,140 169 00:10:42,140 --> 00:10:50,030 So if it doesn't know these matrices are sparse, it will 170 00:10:50,030 --> 00:10:54,620 go through all the steps, not taking advantage of the fact 171 00:10:54,620 --> 00:10:56,750 that we've got all these 0s here. 172 00:10:56,750 --> 00:11:00,380 If it does know that they're sparse, then it's 173 00:11:00,380 --> 00:11:01,500 tremendously fast. 174 00:11:01,500 --> 00:11:04,240 Let me come back to that point. 175 00:11:04,240 --> 00:11:13,970 Maybe actually backslash is smart enough to look to see 176 00:11:13,970 --> 00:11:17,050 whether the matrix, whether sparseness is available. 177 00:11:17,050 --> 00:11:18,330 So I shouldn't have said -- 178 00:11:18,330 --> 00:11:22,600 I think maybe there's a lot engineered into backslash. 179 00:11:22,600 --> 00:11:27,230 Actually, backslash, also engineered in there is the 180 00:11:27,230 --> 00:11:29,120 least squares solution. 181 00:11:29,120 --> 00:11:35,180 If you give it a rectangular problem and, say, too many 182 00:11:35,180 --> 00:11:42,900 equations, so that you can't expect to have an exact 183 00:11:42,900 --> 00:11:46,880 solution, backslash will pick the least squares 184 00:11:46,880 --> 00:11:49,840 solution and much more. 185 00:11:49,840 --> 00:11:55,010 That's probably the most used operation. 186 00:11:55,010 --> 00:11:58,750 So I said something about the Eigen values and everybody 187 00:11:58,750 --> 00:12:06,620 sees that if I multiply this matrix by the values of u at 188 00:12:06,620 --> 00:12:10,870 successive mesh points, I'll get the second difference that 189 00:12:10,870 --> 00:12:12,980 corresponds to uxx. 190 00:12:12,980 --> 00:12:17,360 Now this would cause this matrix -- 191 00:12:17,360 --> 00:12:21,350 so that tells me I'm taking a finite difference. 192 00:12:21,350 --> 00:12:24,900 That plus tells me I'm going in the forward direction, so 193 00:12:24,900 --> 00:12:32,530 that's 1 at the mesh value to the right minus 1 of the mesh 194 00:12:32,530 --> 00:12:34,740 value at the center point. 195 00:12:34,740 --> 00:12:37,860 Of course, this has to be divided by delta x and that by 196 00:12:37,860 --> 00:12:39,260 delta x squared. 197 00:12:39,260 --> 00:12:46,940 So these are matrices, along with the backward difference 198 00:12:46,940 --> 00:12:53,600 and the center difference, out of which you build the basic 199 00:12:53,600 --> 00:12:57,540 finite difference equation, as you've done. 200 00:12:57,540 --> 00:13:02,050 I want to make a comment here though, about now on this 201 00:13:02,050 --> 00:13:06,900 topic of Eigen values. 202 00:13:06,900 --> 00:13:11,500 Eigen values for k really tell you the truth 203 00:13:11,500 --> 00:13:14,060 about the matrix k. 204 00:13:14,060 --> 00:13:18,120 The Eigen values of that matrix k start just a little 205 00:13:18,120 --> 00:13:25,270 above 0 and they go to a little before 4. 206 00:13:25,270 --> 00:13:27,760 So the Eigen values for k -- 207 00:13:27,760 --> 00:13:30,560 208 00:13:30,560 --> 00:13:35,010 so I put that here, the Eigen values of k are 209 00:13:35,010 --> 00:13:36,880 between 0 and 1. 210 00:13:36,880 --> 00:13:43,180 211 00:13:43,180 --> 00:13:47,610 They come very close to 4 and quite close to 0, depending on 212 00:13:47,610 --> 00:13:51,840 the size of the matrix of course. 213 00:13:51,840 --> 00:13:56,520 Let me just do -- if I took the one by one case, its Eigen 214 00:13:56,520 --> 00:13:57,950 value is 2. 215 00:13:57,950 --> 00:14:04,270 If I took the two by two case, its Eigen values are 1 and 3. 216 00:14:04,270 --> 00:14:08,490 Notice nice properties there. 217 00:14:08,490 --> 00:14:13,340 The Eigen values 1 and 3 are positive, as we said. 218 00:14:13,340 --> 00:14:17,860 This matrix k has positive Eigen values, whatever side. 219 00:14:17,860 --> 00:14:25,550 What's more, the 1 and 3 kind of interlace the 2. 220 00:14:25,550 --> 00:14:28,820 So what I'm saying is, the Eigen value for that is in 221 00:14:28,820 --> 00:14:34,750 between the Eigen value for the two by two and the two 222 00:14:34,750 --> 00:14:39,820 Eigen values 1 and 3 are in between the three Eigen values 223 00:14:39,820 --> 00:14:43,460 that I would get for the three by three case. 224 00:14:43,460 --> 00:14:44,960 Maybe I just write those down. 225 00:14:44,960 --> 00:14:46,700 Those are useful numbers. 226 00:14:46,700 --> 00:14:52,890 So k 2 as lambda equal 1 and 3. 227 00:14:52,890 --> 00:14:56,560 The three by three one, I think the Eigen values are 2 228 00:14:56,560 --> 00:15:03,950 minus root 2, which is smaller than 1, 2 which is in between 229 00:15:03,950 --> 00:15:08,250 and 2 plus root 2, which is larger than 3. 230 00:15:08,250 --> 00:15:12,300 Of course, they're all between 0 and 4. 231 00:15:12,300 --> 00:15:13,130 Just a comment. 232 00:15:13,130 --> 00:15:15,980 How do I know they're between 0 and 4? 233 00:15:15,980 --> 00:15:18,820 234 00:15:18,820 --> 00:15:25,480 There's a somewhat handy little rule for getting the 235 00:15:25,480 --> 00:15:29,600 location of Eigen values, that's just worth knowing as a 236 00:15:29,600 --> 00:15:33,320 sort of general principle, but of course it can't tell you 237 00:15:33,320 --> 00:15:35,440 exactly where they are. 238 00:15:35,440 --> 00:15:39,920 First of all, the fact that the matrix is the metric tells 239 00:15:39,920 --> 00:15:42,750 us what about the Eigen values? 240 00:15:42,750 --> 00:15:45,870 So we learn a very, very important fact about the Eigen 241 00:15:45,870 --> 00:15:50,240 values from just looking at the matrix and observing that 242 00:15:50,240 --> 00:15:51,700 it's symmetric. 243 00:15:51,700 --> 00:15:55,690 That tells us that the Eigen values are real. 244 00:15:55,690 --> 00:15:56,940 They're real numbers. 245 00:15:56,940 --> 00:15:59,460 246 00:15:59,460 --> 00:16:01,520 Actually, it tells us something equally important 247 00:16:01,520 --> 00:16:03,420 about the Eigen vectors. 248 00:16:03,420 --> 00:16:07,710 The Eigen vectors of the matrix are orthogonal. 249 00:16:07,710 --> 00:16:10,670 The symmetric matrix has real Eigen values, 250 00:16:10,670 --> 00:16:12,010 orthogonal Eigen vectors. 251 00:16:12,010 --> 00:16:15,510 That's a little bit of linear algebra to know. 252 00:16:15,510 --> 00:16:19,420 Now why between 0 and 4, though? 253 00:16:19,420 --> 00:16:22,030 254 00:16:22,030 --> 00:16:24,480 There's there's this -- 255 00:16:24,480 --> 00:16:25,210 what's his name? 256 00:16:25,210 --> 00:16:27,510 Gershgorin. 257 00:16:27,510 --> 00:16:32,800 Gershgorin pointed out -- and it's a two line proof -- that 258 00:16:32,800 --> 00:16:36,170 every Eigen value is in one of his -- one 259 00:16:36,170 --> 00:16:38,390 or more of his circles. 260 00:16:38,390 --> 00:16:41,660 So where are the Gershgorin circles? 261 00:16:41,660 --> 00:16:47,310 A typical Gershgorin circle is centered at the number here, 262 00:16:47,310 --> 00:16:54,360 2, that's on the diagonal and its radius is the sum off the 263 00:16:54,360 --> 00:16:57,350 diagonal, but you take absolute values. 264 00:16:57,350 --> 00:17:01,520 Gershgorin wasn't doing any of the fine points that really 265 00:17:01,520 --> 00:17:03,150 locate the Eigen value. 266 00:17:03,150 --> 00:17:08,210 So in this matrix, all the centers are at 2, the 267 00:17:08,210 --> 00:17:15,210 diagonals and the radii are 2, also 2, because that and that 268 00:17:15,210 --> 00:17:16,970 and absolute value make 2. 269 00:17:16,970 --> 00:17:19,630 270 00:17:19,630 --> 00:17:23,750 This first row makes a 1 and actually, that's what -- 271 00:17:23,750 --> 00:17:30,140 that by a little careful argument, is what gets the 272 00:17:30,140 --> 00:17:36,050 Eigen values not actually touching 0 or touching 4. 273 00:17:36,050 --> 00:17:37,570 It takes a little patience. 274 00:17:37,570 --> 00:17:40,520 All you could say from here -- 275 00:17:40,520 --> 00:17:44,130 all Gershgorin could say what would be, the Eigen values are 276 00:17:44,130 --> 00:17:48,960 in a circle, centered at 2, its radius is 2, so they're 277 00:17:48,960 --> 00:17:51,770 between 0 and 4. 278 00:17:51,770 --> 00:17:56,460 Then it's that first and last row -- either the first or the 279 00:17:56,460 --> 00:18:05,240 last row would do to say that they're strictly positive. 280 00:18:05,240 --> 00:18:11,130 Of course, the true second difference, I should divide k 281 00:18:11,130 --> 00:18:13,640 by delta x squared. 282 00:18:13,640 --> 00:18:17,450 So the Eigen values will be divided by delta x squared 283 00:18:17,450 --> 00:18:19,320 divided by a small number, so they will 284 00:18:19,320 --> 00:18:22,790 really be much larger. 285 00:18:22,790 --> 00:18:26,870 The ratio of the biggest to the smallest isn't affected by 286 00:18:26,870 --> 00:18:31,020 the delta x squared and that's a key number. 287 00:18:31,020 --> 00:18:35,120 Let me put that maybe on the next board for k. 288 00:18:35,120 --> 00:18:38,530 289 00:18:38,530 --> 00:18:43,890 So lambda max is about 5. 290 00:18:43,890 --> 00:18:53,170 Lambda min, the smallest Eigen value is close to 0. 291 00:18:53,170 --> 00:18:55,340 How close? 292 00:18:55,340 --> 00:18:59,450 It's of the order of some constant over n squared. 293 00:18:59,450 --> 00:19:03,380 294 00:19:03,380 --> 00:19:06,830 Now I use the word condition number and that -- 295 00:19:06,830 --> 00:19:08,670 so let me write that down. 296 00:19:08,670 --> 00:19:15,370 Condition number -- say c of k for condition number is the 297 00:19:15,370 --> 00:19:19,120 ratio lambda max over lambda min. 298 00:19:19,120 --> 00:19:21,630 Of course, I'm using here the fact that k 299 00:19:21,630 --> 00:19:23,410 is a symmetric matrix. 300 00:19:23,410 --> 00:19:26,740 Symmetric matrices are so beautiful that their Eigen 301 00:19:26,740 --> 00:19:31,220 values give you a reliable story here. 302 00:19:31,220 --> 00:19:34,360 So 4 divided by this -- 303 00:19:34,360 --> 00:19:37,890 the main point is that it's o of -- 304 00:19:37,890 --> 00:19:39,960 it's a border 1 over n -- 305 00:19:39,960 --> 00:19:40,270 sorry. 306 00:19:40,270 --> 00:19:43,590 When I divide by lambda min, that puts the n squared up in 307 00:19:43,590 --> 00:19:45,390 the numerator. 308 00:19:45,390 --> 00:19:52,650 It's o of n squared, growing like n squared, and that 309 00:19:52,650 --> 00:20:00,820 condition number, somehow it measures how close the matrix 310 00:20:00,820 --> 00:20:10,170 is to being singular, because it involves this lambda min, 311 00:20:10,170 --> 00:20:13,940 which is the smallest Eigen value and would be 0 if it 312 00:20:13,940 --> 00:20:18,000 were singular and it's scaled by lambda max. 313 00:20:18,000 --> 00:20:22,370 So if I'm multiply the matrix by 100, what happens to the 314 00:20:22,370 --> 00:20:23,830 condition number? 315 00:20:23,830 --> 00:20:25,300 No change. 316 00:20:25,300 --> 00:20:29,180 No change, because I'm doing lambda max over lambda min. 317 00:20:29,180 --> 00:20:32,620 Both lambda max and lambda min would be multiplied by 100, 318 00:20:32,620 --> 00:20:35,230 but the ratio wouldn't be different 319 00:20:35,230 --> 00:20:45,040 So this is a useful measure and o of n squared, that's a 320 00:20:45,040 --> 00:20:48,220 big number if n is large. 321 00:20:48,220 --> 00:20:52,040 A big numbers if n is large and that condition number, 322 00:20:52,040 --> 00:20:54,850 where does it come in elimination? 323 00:20:54,850 --> 00:20:58,860 324 00:20:58,860 --> 00:21:02,920 In elimination, the round off error -- 325 00:21:02,920 --> 00:21:06,970 326 00:21:06,970 --> 00:21:14,130 roughly, the rule of thumb is that you would -- 327 00:21:14,130 --> 00:21:19,600 if the condition number is 10 to the eighth, you might lose 328 00:21:19,600 --> 00:21:26,850 eight significant bits in the back slide. 329 00:21:26,850 --> 00:21:28,690 You could. 330 00:21:28,690 --> 00:21:34,800 So this condition number measures how sensitive your 331 00:21:34,800 --> 00:21:38,250 matrix is to round off. 332 00:21:38,250 --> 00:21:46,660 So that's a few thoughts about matrices and that matrix k in 333 00:21:46,660 --> 00:21:47,770 particular. 334 00:21:47,770 --> 00:21:55,960 Now what about the other matrix, the first differenec? 335 00:21:55,960 --> 00:22:02,940 The point I want to make about that matrix is, what about 336 00:22:02,940 --> 00:22:04,600 it's Eigen values? 337 00:22:04,600 --> 00:22:10,470 What are the Eigen values of that upper triangular matrix? 338 00:22:10,470 --> 00:22:15,930 They are, if you remember linear algebra -- but I can 339 00:22:15,930 --> 00:22:20,550 just tell you quickly -- the main point for a triangular 340 00:22:20,550 --> 00:22:25,840 matrix, the Eigen values are sitting on the diagonal. 341 00:22:25,840 --> 00:22:32,150 So this matrix has the Eigen value minus 1 repeated n time. 342 00:22:32,150 --> 00:22:37,800 343 00:22:37,800 --> 00:22:42,650 That true fact is totally misleading, totally 344 00:22:42,650 --> 00:22:43,900 misleading. 345 00:22:43,900 --> 00:22:47,110 346 00:22:47,110 --> 00:22:50,350 The Eigen values for this triangular matrix don't even 347 00:22:50,350 --> 00:22:58,200 notice what I've got above the diagonal and somehow they 348 00:22:58,200 --> 00:23:01,320 can't give a reasonable picture of what the matrix is 349 00:23:01,320 --> 00:23:02,880 actually doing. 350 00:23:02,880 --> 00:23:08,580 So maybe that's my warning here, that for a matrix which 351 00:23:08,580 --> 00:23:11,750 is absolutely not symmetric, right? 352 00:23:11,750 --> 00:23:13,120 I mean, not at all symmetric. 353 00:23:13,120 --> 00:23:15,640 354 00:23:15,640 --> 00:23:20,130 For the center difference, which is -- 355 00:23:20,130 --> 00:23:21,330 what's the center difference? 356 00:23:21,330 --> 00:23:24,110 I was going to say symmetric, but it's the opposite. 357 00:23:24,110 --> 00:23:26,920 Center difference would be -- 358 00:23:26,920 --> 00:23:31,320 let's put delta centered down here. 359 00:23:31,320 --> 00:23:34,050 Center difference would be I'd have a 1. 360 00:23:34,050 --> 00:23:39,080 0s would go on the point that -- 361 00:23:39,080 --> 00:23:41,130 for the central value. 362 00:23:41,130 --> 00:23:46,080 1 would multiply the forward value and minus 1 would 363 00:23:46,080 --> 00:23:49,060 multiply that and then I'd have 1/2 and then I'd probably 364 00:23:49,060 --> 00:23:50,310 have a delta x. 365 00:23:50,310 --> 00:23:52,990 366 00:23:52,990 --> 00:23:59,480 But the main point is, my matrix word look 367 00:23:59,480 --> 00:24:00,680 something like this. 368 00:24:00,680 --> 00:24:04,670 Minus 1 and 1s on two diagonals. 369 00:24:04,670 --> 00:24:09,110 Now we could find the Eigen values of that matrix. 370 00:24:09,110 --> 00:24:14,820 Do you know anything about the Eigen values? 371 00:24:14,820 --> 00:24:20,280 This is a chance for me just to speak for a few minutes 372 00:24:20,280 --> 00:24:24,650 about useful facts that you can tell about a matrix just 373 00:24:24,650 --> 00:24:26,410 by looking at it. 374 00:24:26,410 --> 00:24:30,450 So what do I see when I look at that matrix? 375 00:24:30,450 --> 00:24:33,540 Is it symmetric? 376 00:24:33,540 --> 00:24:35,710 It's the opposite of symmetric, because the 377 00:24:35,710 --> 00:24:39,180 symmetric matrix up there, if I transpose 378 00:24:39,180 --> 00:24:42,020 it, it doesn't change. 379 00:24:42,020 --> 00:24:46,780 If I transpose this one, I'll get some kind of a backward 380 00:24:46,780 --> 00:24:48,500 difference. 381 00:24:48,500 --> 00:24:52,790 If I transpose this one, then the 1s and the 382 00:24:52,790 --> 00:24:54,630 minus 1s will reverse. 383 00:24:54,630 --> 00:24:56,170 I'll get the negative. 384 00:24:56,170 --> 00:25:01,520 So the rule for this center difference is -- so shall I -- 385 00:25:01,520 --> 00:25:03,540 how am I going to call center different? 386 00:25:03,540 --> 00:25:06,840 Del centered, for the moment. 387 00:25:06,840 --> 00:25:12,930 The transpose of that is minus itself. 388 00:25:12,930 --> 00:25:16,100 389 00:25:16,100 --> 00:25:17,350 So what does that tell me? 390 00:25:17,350 --> 00:25:21,330 391 00:25:21,330 --> 00:25:27,240 First, that matrix is -- 392 00:25:27,240 --> 00:25:30,390 393 00:25:30,390 --> 00:25:32,510 it's the opposite of symmetric, but 394 00:25:32,510 --> 00:25:35,130 it's actually OK. 395 00:25:35,130 --> 00:25:39,910 What I mean by OK is, its Eigen vectors -- 396 00:25:39,910 --> 00:25:42,870 we're back to orthogonal Eigen vectors. 397 00:25:42,870 --> 00:25:46,090 I didn't say anything about the Eigen vectors of del plus, 398 00:25:46,090 --> 00:25:49,990 but actually that was the biggest problem. 399 00:25:49,990 --> 00:25:55,010 This matrix del plus has one Eigen value repeated n time 400 00:25:55,010 --> 00:26:00,360 and it has only one Eigen vector, not -- 401 00:26:00,360 --> 00:26:02,970 it doesn't even have a full set of Eigen vectors, much 402 00:26:02,970 --> 00:26:06,060 less orthogonal ones. 403 00:26:06,060 --> 00:26:10,370 So that matrix is like -- 404 00:26:10,370 --> 00:26:13,540 you don't want to trust the Eigen value picture that you 405 00:26:13,540 --> 00:26:15,380 get from a matrix like that. 406 00:26:15,380 --> 00:26:20,210 Here this anti-symmetric matrix can be trusted. 407 00:26:20,210 --> 00:26:22,860 Its Eigen value picture is reliable. 408 00:26:22,860 --> 00:26:25,130 It does tell you what's going on. 409 00:26:25,130 --> 00:26:29,000 The Eigen vectors are orthogonal. 410 00:26:29,000 --> 00:26:31,990 They're complex, actually. 411 00:26:31,990 --> 00:26:36,920 Actually, they'll look a lot like our e to the ikxs. 412 00:26:36,920 --> 00:26:42,430 So we don't panic when we see complex Eigen values. 413 00:26:42,430 --> 00:26:45,990 The Eigen values are -- do you know what the Eigen values 414 00:26:45,990 --> 00:26:50,470 looks like for anti-symmetric matrix? 415 00:26:50,470 --> 00:26:56,180 They're pure imaginary, just the way that when we took 416 00:26:56,180 --> 00:26:57,580 second differences -- 417 00:26:57,580 --> 00:27:00,580 418 00:27:00,580 --> 00:27:08,270 maybe I'll just put here the center difference, the 419 00:27:08,270 --> 00:27:14,770 centered first difference, when we applied it to -- 420 00:27:14,770 --> 00:27:20,680 I want apply to eo to the ikx to find it's what 421 00:27:20,680 --> 00:27:22,320 factor comes out. 422 00:27:22,320 --> 00:27:30,040 So I get e to the ik plus 1 k plus 1 delta x 423 00:27:30,040 --> 00:27:32,740 from the plus side. 424 00:27:32,740 --> 00:27:35,990 425 00:27:35,990 --> 00:27:39,990 The is the matrix I'm doing with 1 and minus 1. 426 00:27:39,990 --> 00:27:46,130 So the minus 1 will get me minus e to the ik minus 1 427 00:27:46,130 --> 00:27:51,290 delta x and of course, I factor out of that the e to 428 00:27:51,290 --> 00:27:55,010 the ikxs, so I'm left with e to the -- 429 00:27:55,010 --> 00:27:59,590 the thing that factors out is e to the i delta x minus e to 430 00:27:59,590 --> 00:28:03,380 the e minus i delta x -- and what's that? 431 00:28:03,380 --> 00:28:08,350 That multiplies the eo to the ikx, the Eigen vector. 432 00:28:08,350 --> 00:28:11,510 This is like the Eigen value and what do I 433 00:28:11,510 --> 00:28:12,850 say about that quantity? 434 00:28:12,850 --> 00:28:15,390 435 00:28:15,390 --> 00:28:22,740 Of course, it's 2 i sine delta x. 436 00:28:22,740 --> 00:28:31,200 Pure imaginary and I should have divided by the 2, which 437 00:28:31,200 --> 00:28:34,830 would take away that 2. 438 00:28:34,830 --> 00:28:36,190 So it's pure imaginary. 439 00:28:36,190 --> 00:28:40,130 440 00:28:40,130 --> 00:28:46,890 In reality and in this Fourier analysis, both are giving this 441 00:28:46,890 --> 00:28:49,080 understanding of what i is. 442 00:28:49,080 --> 00:28:58,400 So that when we did this sort of operation, von Neumann's 443 00:28:58,400 --> 00:29:02,810 rule of following the exponential, we got something 444 00:29:02,810 --> 00:29:05,280 reasonable. 445 00:29:05,280 --> 00:29:11,300 When we do it with this one, it's von Neumann that's 446 00:29:11,300 --> 00:29:15,040 reliable and the Eigen values that are not reliable. 447 00:29:15,040 --> 00:29:18,450 So the Eigen values of this being all minus 1s is 448 00:29:18,450 --> 00:29:22,470 nonsense, doesn't tell us what the Fourier difference 449 00:29:22,470 --> 00:29:25,020 operator is really doing. 450 00:29:25,020 --> 00:29:30,290 But von Neumann tells us what is truly going on. 451 00:29:30,290 --> 00:29:33,930 Of course, that would be the same thing in which this minus 452 00:29:33,930 --> 00:29:38,050 1 wouldn't appear and the 2 wouldn't appear. 453 00:29:38,050 --> 00:29:40,790 So what would we get out of von Neumann? 454 00:29:40,790 --> 00:29:44,230 So this is for delta plus. 455 00:29:44,230 --> 00:29:49,500 I would factor out an e to the i delta x minus 1. 456 00:29:49,500 --> 00:29:52,250 457 00:29:52,250 --> 00:29:54,910 That's what would multiply it e to the ikx. 458 00:29:54,910 --> 00:29:59,530 Oh, e to the i -- sorry. 459 00:29:59,530 --> 00:30:01,230 Yes, that's right. 460 00:30:01,230 --> 00:30:05,570 That would multiple e to the ik delta x. 461 00:30:05,570 --> 00:30:10,860 Sorry, should've had delta x there, but I wasn't paying 462 00:30:10,860 --> 00:30:11,990 attention to that. 463 00:30:11,990 --> 00:30:14,030 Here I was paying attention to this 464 00:30:14,030 --> 00:30:16,230 and it was pure imaginary. 465 00:30:16,230 --> 00:30:18,300 Here I'm paying attention -- 466 00:30:18,300 --> 00:30:21,770 here von Neumann at least is paying attention to this and 467 00:30:21,770 --> 00:30:25,590 what's he seeing? 468 00:30:25,590 --> 00:30:32,160 Not pure imaginary or purely real, off in the complex plane 469 00:30:32,160 --> 00:30:46,700 and that's really what the rights growth factor or the 470 00:30:46,700 --> 00:30:52,470 right number to associate with frequency k for this forward 471 00:30:52,470 --> 00:30:54,690 difference. 472 00:30:54,690 --> 00:30:58,710 So I guess I'm saying that von Neumann does -- 473 00:30:58,710 --> 00:31:04,420 did the right thing to come up with these pictures for the 474 00:31:04,420 --> 00:31:06,880 growth factors. 475 00:31:06,880 --> 00:31:11,850 Eigen values confirm that and really pin it down when 476 00:31:11,850 --> 00:31:13,200 they're reliable. 477 00:31:13,200 --> 00:31:17,100 Eigen vectors and Eigen values are reliable when Eigen 478 00:31:17,100 --> 00:31:20,880 vectors are orthogonal and that's for matrices that are 479 00:31:20,880 --> 00:31:23,290 symmetric or anti-symmetric. 480 00:31:23,290 --> 00:31:26,120 481 00:31:26,120 --> 00:31:29,000 There's a little bit larger class of matrices that include 482 00:31:29,000 --> 00:31:35,570 orthogonal matrices, but beyond that -- 483 00:31:35,570 --> 00:31:39,370 actually, there's been a lot of discussion over many years 484 00:31:39,370 --> 00:31:51,590 of Eigen values and the -- 485 00:31:51,590 --> 00:31:54,880 for problems that are not controlled by symmetric or 486 00:31:54,880 --> 00:31:56,440 anti-symmetric matrices. 487 00:31:56,440 --> 00:32:00,460 488 00:32:00,460 --> 00:32:05,060 The alternative, the more refined idea of pseudo-Eigen 489 00:32:05,060 --> 00:32:12,890 values is now appearing in an important book by Trefethen 490 00:32:12,890 --> 00:32:16,670 and Embry, and with many examples -- 491 00:32:16,670 --> 00:32:18,330 OK, I won't pursue that. 492 00:32:18,330 --> 00:32:19,030 Right. 493 00:32:19,030 --> 00:32:28,300 So this is some basic fact about those matrices, all of 494 00:32:28,300 --> 00:32:30,680 which are one dimensional. 495 00:32:30,680 --> 00:32:37,500 Now this board prepares the way to get into 2D and 3D. 496 00:32:37,500 --> 00:32:42,910 So I just want to ask, what does the -- 497 00:32:42,910 --> 00:32:46,900 we didn't really do the heat equation or the wave equation 498 00:32:46,900 --> 00:32:52,170 in 2D, but we could have. 499 00:32:52,170 --> 00:32:59,530 The von Neumann test would be straightforward, but now I 500 00:32:59,530 --> 00:33:01,580 want to think about the matrices. 501 00:33:01,580 --> 00:33:06,150 What does the two dimensional second 502 00:33:06,150 --> 00:33:11,350 difference matrix look like? 503 00:33:11,350 --> 00:33:15,040 What I'm going to do, just to look ahead, I'm going to use 504 00:33:15,040 --> 00:33:20,590 MATLAB's operation called kron, short for Kronecker, to 505 00:33:20,590 --> 00:33:27,580 create a 2D matrix out of this 1D center difference. 506 00:33:27,580 --> 00:33:31,390 So if I think now about center differences, second 507 00:33:31,390 --> 00:33:32,730 differences -- 508 00:33:32,730 --> 00:33:38,150 so I'm approximating uxx plus uyy -- 509 00:33:38,150 --> 00:33:44,140 or really, I'm approximating minus uxx minus uyy, because 510 00:33:44,140 --> 00:33:47,620 that k approximates minus the second difference. 511 00:33:47,620 --> 00:33:48,870 What do I -- 512 00:33:48,870 --> 00:33:51,240 513 00:33:51,240 --> 00:33:54,430 what do my matrices look like? 514 00:33:54,430 --> 00:33:56,590 What's their bandwidth? 515 00:33:56,590 --> 00:33:58,540 How expensive is it to invert them? 516 00:33:58,540 --> 00:34:00,390 These are the key questions. 517 00:34:00,390 --> 00:34:08,460 What's the matrix k 2 d that corresponds to -- 518 00:34:08,460 --> 00:34:12,460 gives me second differences in the x direction plus second 519 00:34:12,460 --> 00:34:15,120 differences in the y direction. 520 00:34:15,120 --> 00:34:18,630 So I'll write k 2 d for that matrix. 521 00:34:18,630 --> 00:34:20,060 Let's get some picture of it. 522 00:34:20,060 --> 00:34:23,300 523 00:34:23,300 --> 00:34:29,500 First of all, let me imagine that I'm on a squred with a 524 00:34:29,500 --> 00:34:30,990 square grid. 525 00:34:30,990 --> 00:34:44,440 Delta x in both directions Square grid, let me say n mesh 526 00:34:44,440 --> 00:34:46,700 points each way. 527 00:34:46,700 --> 00:34:50,280 So n, I don't know whether I'm counting -- right now, I won't 528 00:34:50,280 --> 00:34:53,070 worry whether I'm counting the boundary ones or not. 529 00:34:53,070 --> 00:34:54,350 Probably not. 530 00:34:54,350 --> 00:34:56,710 So n -- 531 00:34:56,710 --> 00:35:03,635 I'll say n point, point n, n points -- so n delta x and in 532 00:35:03,635 --> 00:35:08,630 this direction n delta x. 533 00:35:08,630 --> 00:35:10,740 So my matrix is a border. 534 00:35:10,740 --> 00:35:18,950 It's of size n squared, the number of unknowns. 535 00:35:18,950 --> 00:35:21,080 Now I will be a little more careful. 536 00:35:21,080 --> 00:35:25,000 Here, let me take the boundary values as given. 537 00:35:25,000 --> 00:35:26,480 They're not unknown. 538 00:35:26,480 --> 00:35:29,380 So n in this picture is 4. 539 00:35:29,380 --> 00:35:35,980 One, two, three, four unknowns there on a typical row. 540 00:35:35,980 --> 00:35:39,330 Now I have to give them a new number -- five, six, seven, 541 00:35:39,330 --> 00:35:47,190 eight, nine, 10, 11, 12, 13, 14, 15, 16 -- 542 00:35:47,190 --> 00:35:54,600 and n being 4, n squared is 16 for that particular square. 543 00:35:54,600 --> 00:35:56,800 So my matrix is 16 by 16. 544 00:35:56,800 --> 00:36:00,970 545 00:36:00,970 --> 00:36:06,900 But somehow I want to be able to create it out of 4 by 4 546 00:36:06,900 --> 00:36:08,460 matrices like k. 547 00:36:08,460 --> 00:36:12,435 So k 1 d, which I'm just going to call k -- 548 00:36:12,435 --> 00:36:15,430 549 00:36:15,430 --> 00:36:18,110 kn will be the 4 by 4 one. 550 00:36:18,110 --> 00:36:19,360 2 minus 1 -- 551 00:36:19,360 --> 00:36:24,340 552 00:36:24,340 --> 00:36:28,750 so that's the matrix that gives me second differences 553 00:36:28,750 --> 00:36:35,610 along a typical row or down a typical column. 554 00:36:35,610 --> 00:36:37,540 But now what am I looking for? 555 00:36:37,540 --> 00:36:39,690 I'm looking to do both -- 556 00:36:39,690 --> 00:36:42,430 second differences in a row and a column. 557 00:36:42,430 --> 00:36:47,320 So if I pick a typical mesh point, like number 11. 558 00:36:47,320 --> 00:36:50,100 559 00:36:50,100 --> 00:36:52,000 Mesh point 11 -- 560 00:36:52,000 --> 00:36:54,740 let me blow up this picture here. 561 00:36:54,740 --> 00:36:59,270 It's going to be influenced, mesh point 11, by 10 and 12. 562 00:36:59,270 --> 00:37:02,640 The second difference is in the x direction and by 7 and 563 00:37:02,640 --> 00:37:08,120 15, notice those are not so close to 10 or 11. 564 00:37:08,120 --> 00:37:11,410 The second differences is in the y direction, so let me 565 00:37:11,410 --> 00:37:12,590 blow that up. 566 00:37:12,590 --> 00:37:16,140 So here's mesh point number 11 corresponding to 567 00:37:16,140 --> 00:37:20,970 row 11 of k 2 d. 568 00:37:20,970 --> 00:37:25,540 569 00:37:25,540 --> 00:37:27,890 So I guess I'm asking what role 11 of k 570 00:37:27,890 --> 00:37:30,530 2 d will look like. 571 00:37:30,530 --> 00:37:36,300 So here's mesh point 9, 10 and 12, so I have a second 572 00:37:36,300 --> 00:37:41,740 difference in the x direction from uxx but minus uxx -- 573 00:37:41,740 --> 00:37:45,550 that means I can put a minus 1 there, a 2 there 574 00:37:45,550 --> 00:37:47,900 and a minus 1 there. 575 00:37:47,900 --> 00:37:54,300 Now I have the same in the y direction with 15 and 7, so I 576 00:37:54,300 --> 00:38:03,530 have a minus 1 in column 15, a minus 1 in column 7, so I have 577 00:38:03,530 --> 00:38:11,420 a 4 minus 1 and then two more for the center gives me a 4. 578 00:38:11,420 --> 00:38:15,460 So a typical row will have -- 579 00:38:15,460 --> 00:38:17,750 it'll be sparse, of course -- 580 00:38:17,750 --> 00:38:22,170 it'll have a minus 1 in positions 7, a minus 1 in 581 00:38:22,170 --> 00:38:28,610 position 10, a 4, a minus 1 and a minus 1 over there in 582 00:38:28,610 --> 00:38:31,160 position 15. 583 00:38:31,160 --> 00:38:34,530 That's a typical row of k 2 d. 584 00:38:34,530 --> 00:38:35,780 It adds to 0. 585 00:38:35,780 --> 00:38:39,130 586 00:38:39,130 --> 00:38:46,940 If Gershgorin got his hands on this matrix, he would say that 587 00:38:46,940 --> 00:38:51,200 since all the rows -- the 4 will be on -- 588 00:38:51,200 --> 00:38:52,820 will the 4 be on the diagonal? 589 00:38:52,820 --> 00:38:58,180 Yes, the 4 will be on the diagonal all the way. 590 00:38:58,180 --> 00:39:03,020 I guess let's see a little bit more clearly what the matrix k 591 00:39:03,020 --> 00:39:04,270 2 d looks like. 592 00:39:04,270 --> 00:39:06,800 593 00:39:06,800 --> 00:39:10,910 This is probably the most studied matrix in numerical 594 00:39:10,910 --> 00:39:17,140 analysis because his its a model of what stays nice and 595 00:39:17,140 --> 00:39:22,090 what gets more difficult as you move into two dimensions. 596 00:39:22,090 --> 00:39:24,180 So some things certainly stay nice. 597 00:39:24,180 --> 00:39:26,020 Symmetries -- 598 00:39:26,020 --> 00:39:32,000 so properties of k 2 d, k to d will be -- it'll 599 00:39:32,000 --> 00:39:33,250 be symmetric again. 600 00:39:33,250 --> 00:39:35,940 601 00:39:35,940 --> 00:39:37,610 It'll be positive definite again. 602 00:39:37,610 --> 00:39:42,930 603 00:39:42,930 --> 00:39:45,780 So what does k 2 d -- 604 00:39:45,780 --> 00:39:53,020 it's 16 by 16 and a typical row looks like that. 605 00:39:53,020 --> 00:39:56,180 That's a typical interior row. 606 00:39:56,180 --> 00:40:00,380 What does maybe -- if I took the first row, what does the 607 00:40:00,380 --> 00:40:03,810 very first row look like if I put row one above it? 608 00:40:03,810 --> 00:40:07,410 609 00:40:07,410 --> 00:40:09,960 Let me draw row one. 610 00:40:09,960 --> 00:40:12,730 So what's the difference with row one? 611 00:40:12,730 --> 00:40:15,070 It's these are boundary values. 612 00:40:15,070 --> 00:40:17,110 These are not -- 613 00:40:17,110 --> 00:40:18,400 these are going to show up on the right 614 00:40:18,400 --> 00:40:20,360 hand side of the equation. 615 00:40:20,360 --> 00:40:21,380 They're known numbers. 616 00:40:21,380 --> 00:40:23,810 They're not -- they don't involve unknown things, so the 617 00:40:23,810 --> 00:40:26,460 only neighbors are 2 and 5. 618 00:40:26,460 --> 00:40:30,320 So I'll still have the second difference, minus 12 minus 1 619 00:40:30,320 --> 00:40:35,640 and minus 12 minus 1 -- still this five point molecule with 620 00:40:35,640 --> 00:40:40,060 four at the center, but there won't be so many neighbors. 621 00:40:40,060 --> 00:40:43,030 There'll be the neighbor at the -- 622 00:40:43,030 --> 00:40:45,320 just to the right. 623 00:40:45,320 --> 00:40:47,990 Neighbor number two and there'll be neighbor number 624 00:40:47,990 --> 00:40:50,270 five a little further along and that's it. 625 00:40:50,270 --> 00:40:52,820 626 00:40:52,820 --> 00:40:58,060 It's like the 2 minus 1 boundary row. 627 00:40:58,060 --> 00:41:02,260 It's a boundary row and a boundary row hasn't got as 628 00:41:02,260 --> 00:41:05,970 many minus 1s because it hasn't got as 629 00:41:05,970 --> 00:41:10,020 many neighboring unknowns. 630 00:41:10,020 --> 00:41:12,940 That boundary row would have three neighbors. 631 00:41:12,940 --> 00:41:17,380 Row two would have a 4 minus 1 minus 1, but not -- 632 00:41:17,380 --> 00:41:18,720 nobody there. 633 00:41:18,720 --> 00:41:23,710 So now I'm going to try to draw k 2 d. 634 00:41:23,710 --> 00:41:26,140 Let me try to draw k to d. 635 00:41:26,140 --> 00:41:27,940 I can do it. 636 00:41:27,940 --> 00:41:38,290 k 2 d will have, from the uxx, the second differences along 637 00:41:38,290 --> 00:41:40,460 the rows, it will have -- 638 00:41:40,460 --> 00:41:43,900 I'll have a row, row one, it'll have 639 00:41:43,900 --> 00:41:46,350 another k on row two. 640 00:41:46,350 --> 00:41:54,280 It'll have a k on -- a k for each row. 641 00:41:54,280 --> 00:41:56,180 These are blocks now. 642 00:41:56,180 --> 00:41:58,290 That's of size n by n. 643 00:41:58,290 --> 00:42:00,495 So all of those are, so the whole thing is n 644 00:42:00,495 --> 00:42:02,780 squared by n squared. 645 00:42:02,780 --> 00:42:06,180 Actually, I'll stop here. 646 00:42:06,180 --> 00:42:14,830 If I wanted to create that matrix with the same k on -- 647 00:42:14,830 --> 00:42:18,770 it somehow the identity is in there and the matrix k is in 648 00:42:18,770 --> 00:42:20,510 there and that's -- 649 00:42:20,510 --> 00:42:23,210 650 00:42:23,210 --> 00:42:23,590 let's see. 651 00:42:23,590 --> 00:42:26,530 It's one or the other of those. 652 00:42:26,530 --> 00:42:29,810 I guess it's the first one. 653 00:42:29,810 --> 00:42:32,000 So what's this Kronecker product? 654 00:42:32,000 --> 00:42:35,770 Now I'm saying what this construction is. 655 00:42:35,770 --> 00:42:41,270 It's very valuable, because it allows you to create matrices. 656 00:42:41,270 --> 00:42:45,320 If you created k as a sparse matrix and i as a sparse 657 00:42:45,320 --> 00:42:49,470 matrix, then the Kronecker product would be automatically 658 00:42:49,470 --> 00:42:51,950 dealt with as a sparse matrix. 659 00:42:51,950 --> 00:42:54,740 So what's the rule for a Kronecker product? 660 00:42:54,740 --> 00:43:00,090 You take the first matrix, which is the identity. 661 00:43:00,090 --> 00:43:04,350 662 00:43:04,350 --> 00:43:05,600 The rest 0s. 663 00:43:05,600 --> 00:43:08,740 664 00:43:08,740 --> 00:43:11,790 So that's i. 665 00:43:11,790 --> 00:43:13,110 Then -- 666 00:43:13,110 --> 00:43:18,650 so that's 1 d and then you multiple -- 667 00:43:18,650 --> 00:43:25,180 each entry in i becomes a block with entry aij times 668 00:43:25,180 --> 00:43:27,220 this guy k. 669 00:43:27,220 --> 00:43:29,990 This'll be the 0 block, this'll be the k block, 670 00:43:29,990 --> 00:43:31,490 this'll be the k block. 671 00:43:31,490 --> 00:43:35,810 I take those 1s and multiply k and those 0s and multiple k 672 00:43:35,810 --> 00:43:38,450 and that's what I get. 673 00:43:38,450 --> 00:43:43,290 So you see now the Kronecker product is a bigger guy. 674 00:43:43,290 --> 00:43:52,940 If matrix a was p by p and matrix b was q by q, then the 675 00:43:52,940 --> 00:43:57,570 Kronecker product would be p times q by p times q. 676 00:43:57,570 --> 00:43:59,000 It would be square again. 677 00:43:59,000 --> 00:44:02,360 678 00:44:02,360 --> 00:44:06,160 It would be symmetric if a and b are symmetric. 679 00:44:06,160 --> 00:44:09,290 Actually, it would have various nice properties. 680 00:44:09,290 --> 00:44:12,920 Its Eigen values would be the products of the Eigen values 681 00:44:12,920 --> 00:44:16,910 of a times the Eigen values of b. 682 00:44:16,910 --> 00:44:22,330 It's a very handy construction and here we saw it in a pretty 683 00:44:22,330 --> 00:44:26,250 easy case where a was only the identity. 684 00:44:26,250 --> 00:44:28,150 Let me do this. 685 00:44:28,150 --> 00:44:31,960 What does the Kronecker rule produce here? 686 00:44:31,960 --> 00:44:38,200 So I take this first matrix and I put it in here, 2 minus 687 00:44:38,200 --> 00:44:43,430 1 minus 1, 2 minus 1 minus 12. 688 00:44:43,430 --> 00:44:47,890 689 00:44:47,890 --> 00:44:52,200 So that's the matrix k and now each of those numbers 690 00:44:52,200 --> 00:44:56,130 multiplies the second thing, which here is i. 691 00:44:56,130 --> 00:45:04,210 So it's 2 i minus i minus i 2 i minus i minus i minus i 692 00:45:04,210 --> 00:45:06,770 minus i 2 i and 2 i. 693 00:45:06,770 --> 00:45:10,280 694 00:45:10,280 --> 00:45:13,670 Now that is the second difference matrix that does 695 00:45:13,670 --> 00:45:14,920 all the columns. 696 00:45:14,920 --> 00:45:17,650 697 00:45:17,650 --> 00:45:21,060 When I add those -- so now I'm going to add that to that. 698 00:45:21,060 --> 00:45:23,840 699 00:45:23,840 --> 00:45:26,530 They're both size n squared. 700 00:45:26,530 --> 00:45:28,450 They give me k to d. 701 00:45:28,450 --> 00:45:34,470 So the neat construction of k 2 d is Kronecker product kron 702 00:45:34,470 --> 00:45:37,810 of ik plus kron of ki. 703 00:45:37,810 --> 00:45:40,940 That's the matrix and let's look at what it 704 00:45:40,940 --> 00:45:45,120 actually looks like. 705 00:45:45,120 --> 00:45:48,920 We're seeing it block wise here. 706 00:45:48,920 --> 00:45:56,700 We saw it row wise here and maybe now we can take one more 707 00:45:56,700 --> 00:45:59,200 look at it, assemble it. 708 00:45:59,200 --> 00:46:00,450 So k 2 d -- 709 00:46:00,450 --> 00:46:03,940 710 00:46:03,940 --> 00:46:10,260 I plan to add that matrix to that matrix to get k 2 d. 711 00:46:10,260 --> 00:46:12,090 So it will have -- 712 00:46:12,090 --> 00:46:16,140 since they both have 2s on the diagonal, it'll have 4s on the 713 00:46:16,140 --> 00:46:21,460 diagonal, so 4s all the way, but it'll be block wise. 714 00:46:21,460 --> 00:46:24,060 715 00:46:24,060 --> 00:46:28,420 Up here, this block is k plus 2 i. 716 00:46:28,420 --> 00:46:31,010 So that block is -- 717 00:46:31,010 --> 00:46:32,280 goes down to 4. 718 00:46:32,280 --> 00:46:36,870 719 00:46:36,870 --> 00:46:44,950 Now the k contributed minus 1s next to the diagonal, I guess 720 00:46:44,950 --> 00:46:51,740 that's it, right? k plus 2 i has that block as -- 721 00:46:51,740 --> 00:46:54,120 that's the one, one block. 722 00:46:54,120 --> 00:46:55,840 Why is it -- 723 00:46:55,840 --> 00:46:58,000 so we're seeing -- 724 00:46:58,000 --> 00:47:00,660 did I get it right? 725 00:47:00,660 --> 00:47:05,990 Yes, so we're seeing the neighbors to the right and 726 00:47:05,990 --> 00:47:13,470 left, but now let me bring in -- only now comes the neighbor 727 00:47:13,470 --> 00:47:17,690 above or below and that comes from this off diagonal block, 728 00:47:17,690 --> 00:47:22,520 minus i, which is then minus 1s to minus 1s. 729 00:47:22,520 --> 00:47:26,800 730 00:47:26,800 --> 00:47:29,260 These are all 0 blocks. 731 00:47:29,260 --> 00:47:35,390 Here will be a minus the identity blocked. 732 00:47:35,390 --> 00:47:39,860 Down another block, the diagonal blocks are all the 733 00:47:39,860 --> 00:47:44,600 same and another one, another minute the identity. 734 00:47:44,600 --> 00:47:47,780 735 00:47:47,780 --> 00:47:53,680 Now we're getting to interior mesh points, where we see 736 00:47:53,680 --> 00:47:55,010 typical rows. 737 00:47:55,010 --> 00:47:59,100 So a typical role has the 4s on the diagonal, the minus 1s 738 00:47:59,100 --> 00:48:04,300 left and right and the minus 1s far left and far right -- 739 00:48:04,300 --> 00:48:06,620 and of course, what I'm going to ask you 740 00:48:06,620 --> 00:48:07,870 is, what's the bandwidth? 741 00:48:07,870 --> 00:48:14,700 742 00:48:14,700 --> 00:48:17,230 We're coming to the key point now. 743 00:48:17,230 --> 00:48:20,290 What's the bandwidth of this matrix? 744 00:48:20,290 --> 00:48:26,750 I only have two non 0s above the diagonal on a typical row, 745 00:48:26,750 --> 00:48:34,030 but I have to wait n diagonals before I get 746 00:48:34,030 --> 00:48:35,540 to the second one. 747 00:48:35,540 --> 00:48:39,470 So the bandwidth is n because I have to wait that long. 748 00:48:39,470 --> 00:48:41,120 Then the operation count -- 749 00:48:41,120 --> 00:48:46,020 750 00:48:46,020 --> 00:48:49,700 if I just do ordinary elimination on this matrix, 751 00:48:49,700 --> 00:48:55,330 the operation will be the size of the matrix times a 752 00:48:55,330 --> 00:48:56,580 bandwidth squared. 753 00:48:56,580 --> 00:48:59,680 754 00:48:59,680 --> 00:49:04,510 We can easily check that that's the right count of 755 00:49:04,510 --> 00:49:06,670 operations for a banded matrix. 756 00:49:06,670 --> 00:49:09,070 This is operations on a banded matrix. 757 00:49:09,070 --> 00:49:12,390 758 00:49:12,390 --> 00:49:13,940 So what do we get? 759 00:49:13,940 --> 00:49:18,110 The size of the matrix is n squared. 760 00:49:18,110 --> 00:49:22,770 The bandwidth is n and it gets squared so we 761 00:49:22,770 --> 00:49:24,020 get n to the fourth. 762 00:49:24,020 --> 00:49:26,810 763 00:49:26,810 --> 00:49:29,360 It's getting up there. 764 00:49:29,360 --> 00:49:34,040 If n is 1,000, we've got a serious sized matrix here. 765 00:49:34,040 --> 00:49:42,010 Still a very sparse matrix, so it's not like give up, but the 766 00:49:42,010 --> 00:49:46,040 question is, does the matrix stay sparse as we do 767 00:49:46,040 --> 00:49:47,360 elimination? 768 00:49:47,360 --> 00:49:52,090 That's the center of the next lecture. 769 00:49:52,090 --> 00:49:54,160 Can we organize elimination? 770 00:49:54,160 --> 00:49:58,110 How closely can we reorganize elimination to preserve all 771 00:49:58,110 --> 00:50:02,640 these zillions of 0s that are between here? 772 00:50:02,640 --> 00:50:06,210 They're easy to preserve down here, way up there, but in 773 00:50:06,210 --> 00:50:14,110 this intermediate, those diagonals tend to fill in and 774 00:50:14,110 --> 00:50:17,490 that's not a happy experience. 775 00:50:17,490 --> 00:50:20,590 And It's even less happy in 3D. 776 00:50:20,590 --> 00:50:24,800 So let me just do this same calculation it for 3D and then 777 00:50:24,800 --> 00:50:25,900 we're done for today. 778 00:50:25,900 --> 00:50:27,410 So k 3 d -- 779 00:50:27,410 --> 00:50:30,110 780 00:50:30,110 --> 00:50:33,820 you might like to think how k 3 d could be created by the 781 00:50:33,820 --> 00:50:35,780 kron operation. 782 00:50:35,780 --> 00:50:37,030 Let me just imagine it. 783 00:50:37,030 --> 00:50:39,690 So what's k 3 d looking like? 784 00:50:39,690 --> 00:50:45,070 I've got three directions, so I have a 6 in the center and 6 785 00:50:45,070 --> 00:50:52,800 minus 1s beside it and so 6 goes on the diagonal of k 3 d. 786 00:50:52,800 --> 00:50:56,530 6 minus 1s go on a typical row and how long do I have to wait 787 00:50:56,530 --> 00:50:58,360 until I reach the last one? 788 00:50:58,360 --> 00:51:02,450 So I'm again going to do the size -- which is -- 789 00:51:02,450 --> 00:51:06,180 the matrix size is going to be like nq and what's the 790 00:51:06,180 --> 00:51:11,680 bandwidth going to be like? 791 00:51:11,680 --> 00:51:13,590 Maybe I'll ask you now. 792 00:51:13,590 --> 00:51:15,720 What do you think for the bandwidth? 793 00:51:15,720 --> 00:51:20,600 How long -- if I just number it in the simplest way - and 794 00:51:20,600 --> 00:51:23,600 that'll be the key next time, is there a better numbering? 795 00:51:23,600 --> 00:51:29,290 But if I just number along rows until the rows fill up a 796 00:51:29,290 --> 00:51:33,750 plane of rows and then I move up to the next, the z 797 00:51:33,750 --> 00:51:39,440 direction to the plane above, then I have to wait -- 798 00:51:39,440 --> 00:51:42,790 799 00:51:42,790 --> 00:51:47,780 this was the x and y, so this gave me a bandwidth of n, but 800 00:51:47,780 --> 00:51:50,270 that's not the bandwidth because I have to wait until 801 00:51:50,270 --> 00:51:53,480 I've finish the whole plane, until I go up to the next 802 00:51:53,480 --> 00:52:00,360 plane and catch this chap, so the bandwidth is n squared. 803 00:52:00,360 --> 00:52:10,250 Then the operations, which are size times bandwidth squared, 804 00:52:10,250 --> 00:52:17,130 we're up to n 7 and that is a really horrifying exponent to 805 00:52:17,130 --> 00:52:19,410 see into the seventh. 806 00:52:19,410 --> 00:52:22,770 That means that even for a moderate -- 807 00:52:22,770 --> 00:52:27,420 a problem in 3D with a moderate number, say 1,000 808 00:52:27,420 --> 00:52:29,670 unknowns at each direction, we have -- 809 00:52:29,670 --> 00:52:32,320 810 00:52:32,320 --> 00:52:42,050 we're looking, in theory, at a cost that we can't afford. 811 00:52:42,050 --> 00:52:47,160 Of course, there's a lot to do here. 812 00:52:47,160 --> 00:52:49,840 So there's a lot to do if I stay with direct methods and 813 00:52:49,840 --> 00:52:54,270 that's what I'll do for the next couple of lectures. 814 00:52:54,270 --> 00:52:58,040 Then it's really in 3D that iterative 815 00:52:58,040 --> 00:53:02,540 methods become essential. 816 00:53:02,540 --> 00:53:07,440 I mean, this one, I could do those by direct methods, 2D, 817 00:53:07,440 --> 00:53:12,890 by a smarter direct method than any I've tried here, but 818 00:53:12,890 --> 00:53:19,370 in 3D, even smarter elimination is facing a 819 00:53:19,370 --> 00:53:27,370 serious exponent and loses to iterative methods. 820 00:53:27,370 --> 00:53:29,020 So that's what's coming, actually. 821 00:53:29,020 --> 00:53:33,400 So today's lecture, you see, with the simplest possible 822 00:53:33,400 --> 00:53:37,890 matrices, what the central questions are. 823 00:53:37,890 --> 00:53:45,610 Thanks and I've got homeworks coming back from Mr. Cho and 824 00:53:45,610 --> 00:53:48,950 I'll collect any that are ready to come 825 00:53:48,950 --> 00:53:50,200 in and see you Wednesday. 826 00:53:50,200 --> 00:53:57,952